package com.coder.algorithm.offer_2;

/**
 * 数字序列中某一位的数字
 *
 * @author yuhushuan
 * @date 2020/6/26 15:36
 */
public class _44_1_DigitsInSequence {


    private static int digitAtIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index must be greater than 0!");
        }

        int digits = 1;

        while (true) {
            int numbers = countOfIntegers(digits);

            if (index < numbers) {
                return digitAtIndex(index, digits);
            }
            index -= digits * numbers;
            digits++;
        }
    }

    private static int countOfIntegers(int digits) {
        if (digits == 1) {
            return 10;
        }
        return 9 * powerBase10(digits - 1);
    }

    private static int digitAtIndex(int index, int digits) {
        int number = beginNumber(digits) + index / digits;

        int indexFromRight = digits - 1 - index % digits;
        for (int i = 0; i < indexFromRight; ++i) {
            number /= 10;
        }
        return number % 10;
    }

    private static int beginNumber(int digits) {
        if (digits == 1) {
            return 10;
        }
        return powerBase10(digits - 1);
    }


    private static int powerBase10(int exponent) {
        int result = 1;
        for (int i = 0; i < exponent; ++i) {
            result *= 10;
        }
        return result;
    }

    private static int digitAtIndex_solution2(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index must be greater than 0!");
        }

        StringBuilder builder = new StringBuilder();
        int number = 0;
        while (builder.length() <= index) {
            builder.append(number++);
        }
        return builder.charAt(index) - '0';
    }

    public static void main(String[] args) {
        // 功能测试
        print(10);
        print(190);
        print(1000);

        // 边界值测试
        print(0);
        print(1);
    }

    private static void print(int index) {
        System.out.println("在数字序列中 " + index + " 位的数字是：");
        System.out.println("方法一：" + digitAtIndex(index));
        System.out.println("方法二：" + digitAtIndex_solution2(index));
        System.out.println();
    }
}
